Color correction or transformation of color images is performed to convert images from one color space to another. Images may be represented using a device independent color space or a device dependent color space. Device independent color spaces represent color images independent from particular input and output devices so as to enable independent color imaging between input and output devices. Generally, a color image is transformed to a device dependent color space of an output device before the color image is rendered to insure that the colormetry of the original image is consistent with its reproduction. Such a transformation is performed regardless of whether the original image is defined in a device dependent color space or in a device independent color space. Closed systems that consist for example of a scanner and a printer that are not interconnected with external devices do not require an original color image to be transformed to a device independent color space. Such closed system have color transformation system that generate a color image represented by a first color space and subsequently convert that color space to a second color space before reproduction. Color transformation systems capable of independent color imaging represent color images in a third or a device independent color space which is readily transferable between a plurality of image output devices.
Color images can be generated by an input image terminal such as a scanner or a color image creation program operating on a color workstation. Color images processed by a scanner or a workstation consists of a two dimensional array of picture elements (pixels). The color of each pixel of an image may be represented using a plurality of color spaces. Scanner output is commonly transformed to a color space of tristimulus values, for example, additive primaries red, green and blue (RGB) color space. These values are typically a linear transformation of the standard XYZ coordinates of CIE color space, or a corrected transform of those values. In the case of computer generated images, the computer workstation is operated by a user to create, edit or view "softcopy" color images on the color monitor of the workstation. Colors selected by the user at the user interface of a workstation can also be defined in a color space of tristimulus values such as additive primaries RGB. These colors are defined in a device independent manner using for example color model transformations that are described in "Color Encoding Standard", Xerox System Integration Standard, Xerox Corp, Palo Alto, Calif., July 1991, XNSS 289107 (The Xerox Color Encoding Standard).
An image generated by an image input terminal must be converted to subtractive primaries cyan, magenta, yellow and black (CMYK) or (simply the CMY) color space before being reproduced on an image output terminal such as a printer. CMY color space is typically used to represent the formulation of colored dyes, inks, or toners on paper. Printers typically operate by adding multiple layers of ink or colorant on each page. The response of the addition of colors by the printer tends to be relatively non-linear. Consequently, colors are defined for a particular printer and accordingly color spaces defined for a printer are device dependent. Thus, a printer receives information in a device independent color space from, for example, a workstation. The printer must then convert that information into its device dependent color space. There exist many different methods to convert between color spaces of images produced at a scanner or a workstation to a color space of images to be produced at a printer. Generally, U.S. Pat. No. 4,500,919 to Schreiber and U.S. Pat. No. 2,790,844 to Neugebauer describe the desirability of operating in a device independent color space with subsequent conversion to a device dependent color space.
Color correction consists of mapping points from a three-dimensional color space to a three-dimensional or four-dimensional color space. This mapping depends on the physical properties of a marking device or printer system which is typically nonlinear (as noted above). An effective approach to solving this problem is to use a coarse three-dimensional lookup table with interpolation. The lookup table provides an arbitrary mapping between different devices and the interpolation reduces the size of the table so that large amounts of memory are not required by the system to store a large number of sample points. In general, a lookup table contains values on a uniform grid for each of the three color coordinates of a color space. For example, the color space is divided into parallelepipeds with table values at the vertex points of the parallelepipeds. (An example of a parallelepiped is shown in FIG. 16.) Interpolation is performed for values of points within the volumes of the parallelepipeds by using their position within the volume and the values of samples at the vertices. A common approach to interpolation is trilinear interpolation which gives a linear weighting of all eight vertices. Alternatively, in tetrahedral interpolation the parallelepiped is divided into tetrahedrons as shown in FIG. 17. The points within each tetrahedron are interpolated based on its four vertices as described in U.S. Pat. No. 4,275,413 to Sakamoto and U.S. Pat. No. 4,477,833 to Clark et al. Tetrahedal interpolation is preferred over alternative interpolation techniques because it is computationally simple and requires the retrieval of only four vertex values rather than eight as in trilinear interpolation.
Specifically, in U.S. Pat. No. 4,275,413 to Sakamoto, information is placed into lookup tables and stored in a memory, where the lookup table relates input color space to output color space. The lookup table is commonly a three dimensional table since color is defined with three variables. In RGB space, at a scanner or computer, space can be defined as three dimensional with black at the origin of a three dimensional coordinate system 0, 0, 0, and white at the maximum of a three dimensional coordinate system which in an 8-bit system, would be located at 255, 255, 255. Each of the three axes radiating from the origin point therefore respectively define red, green, and blue. A similar construct can be made for the printer, with axes representing cyan, magenta, and yellow. In the 8-bit system suggested, there will be, however, over 16 million possible colors (256.sup.3). There are clearly too many values for a 1:1 mapping of RGB to CMY. Accordingly, only a relatively small number of samples are used to do the mapping from RGB to CMY, perhaps on the order of 1,000. Therefore, the lookup tables consist of a set of values which could be said to be the intersections for corners of a set of cubes (or parallelepipeds) mounted on top of one another. Colors falling within each cubic volume can be interpolated from the measured values through tetrahedral interpolation.
A hybrid approach that divides the parallelepiped into prisms, as shown in FIG. 18, and uses triangular interpolation in two dimensions and linear interpolation in the third is described by Kanamori et al. in "A Color Transformation Algorithm using Prism Interpolation" IS&T's 8th International Congress on Advances in Non-Impact Printing Technologies pp. 477-482 (1992). This method requires the retrieval of six vertex values. Variations on how a parallelepiped is subdivided into tetrahedrons has been described by Kanamori et al. in "Color Correction Technique for Hard Copies by 4-Neighbors Interpolation Method", Journal of Imaging Science and Technology Vol. 36, No. 1, pp. 73-80 (1992). This contrasts the decomposition shown in FIG. 17 which offers simplicity in the interpolation calculations. Specifically, the tetrahedrons are elongated in FIG. 17 which can give rise to larger interpolation errors than those for more regular tetrahedrons as in FIG. 19. Alternatively, a decomposition which gives more uniform tetrahedrons as taught by Kanamori et al. is shown in FIG. 20, where two decompositions must be applied to alternate cells. Another technique published by Kasson et al. in "A Tetrahedral Interpolation Technique for Color Space Conversion", SPIE Proceedings Vol. 1909:127-138, (1993), describes adding an additional sample point to the center of each parallelepiped as shown in FIG. 17. The method of adding additional body-centered sample points to decompose parallelepipeds to tetrahedra provides more regular tetrahedrons than those shown in FIG. 17.
The references cited herein are incorporated by reference for their teachings.